Viatcheslav Kourktchi
kourktchi@ukrtop.com
master's degree competitor (faculty of computer engineering and computer science)
research teacher:
Yuri Ladyzhensky

master's work topic:
Parallel algorithms for graph problems solving.

• Ladyzhensky Y.V., Kourktchi V.A. Parallel algorithms for graph independent set problem.   [pdf - in russian] (215 kb)
       Two parallel heuristic algorithms for a maximum independent set problem are given. Goldberg-Spenser's algorithm is modified. An algorithm based on greed heuristic and limited search is considered. Testing results for both algorithms are given and conclusions about precision properties are made.
  

• Kourktchi V.A. Research algorithms that finding maximal independent sets in graphs.    [pdf - in russian] (329 kb)
       In the given work, we present the results of research algorithms that finding maximal independent sets of vertices. The Bron-Kerbosh algorithm is considered, and its updating is made.
  

• Goldberg М., Spenser Т. Constructing maximum independent set in parallel. Russian translation by Kourktchi V.A. [pdf - in russian] (208 kb)
       The task of parallel construction of the greatest independent set given the column is considered. The new determined NC-algorithm for model EREW PRAM is considered. For graphs with n vertices and m edges it uses O ((n + m) /lgn) processors and finishes works during O (log < sup > 3 < /sup > n), reducing in logn both time and amount of used processors, in comparison with the previous determined algorithms deciding a problem, using linear amount of processors. < br >

• Goldberg M., Spenser T. A new parallel algorithm for the maximum independent set problem [pdf] (189 kb)
       From www.cs.rpi.edu/~goldberg/publications/papers-reversed.html
       A new parallel algorithm for the maximum independent set prblem is considered. It runs in O(log⁴N) time when implemented on lirear number of EREW-processors. This is the first deterministic algorithm for the maximum independent set prblem (MIS) whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor
  

• Bomze M., Budinich M., Pardalos P.M., Pelillo M. The maximum clique problem. in: Handbook of combinatorial optimization. – Adison-Wesley Publishing Company: 1998, 2410pp.[pdf] (535 kb)
       From www.dsi.unive.it/~pelillo/papers/chapter-clique.ps.gz
       The maximum clique problem is a classical problem in combinatorial optimization, which finds important applications in different domains. In this paper we try to give a survey of results concerning algorithms, complexity and applications of this problem, and also provide an updated bibliography. Of course, we build upon precursory works with similar goals.